1. Field of Invention
This invention is in the field of computer program compilation, and specifically is directed to optimizing computer programs. In particular, a method is set forth for the removal of invariant branches from instruction loops of a computer program.
2. Description of the Prior Art
After a computer program has been written in a high level language (i.e. Fortran, Pascal, C), a compiler program is typically used to convert this program into a sequence of machine language instructions to be executed by a computer. These machine language instructions are also called object code. There are many ways to express a program written in a high level language in object code. In particular, some object code interpretations of the high level language program will run faster than others. For this reason, compiler systems are often equipped to perform a procedure called code optimization. Code optimization is a technique whereby object code is improved so that a program will execute in less time.
Code optimization can be achieved through numerous methods. Repetitious computations may be deleted. Variables that never change may be replaced with constants. An expression within a loop which is always evaluated identically regardless of loop iteration can be moved to a location outside of the loop.
A particular area of interest in the field of code optimization relates to decreasing the running time of program loops, i.e., sections of programs that repeat. Because computer programs spend a relatively large amount of time executing instructions in loops, a code optimization technique which decreases loop execution time can be extremely useful for improving the execution time of the entire computer program.
A common method of improving loop performance is to relocate a computation that produces the same result each time around the loop to a point in the computer program just before the loop begins execution. In this way the computation need only be done once, when the loop is entered, rather than each time the loop is repeated. Such a computation is called a loop invariant.
U.S. Pat. No. 4,567,574 to Saade et al. relates to a method for optimizing COBOL source programs which include PERFORM statements. Where appropriate, the code for the procedure or simplified linkage code is substituted for the PERFORM statement.
U.S. Pat. No. 4,656,582 to Chaitin et al. relates to an optimization method which uses "code motion" and "common subexpression elimination." For instructions which may use values in memory or values in temporary registers, the optimization method selects the best form of instruction for the context in which it lies.
U.S. Pat. No. 4,773,007 to Kasada et al. relates to a method of data flow analysis for determining array element interdependence as a precursor to program code optimization.